#include "../Basics/BasicStruct.cpp"

// 将小于首节点的元素置于前面,大于首节点的元素放在后面

// 1. 遍历整条链表,首先取到第一个值.
// 2. 如果值小头插放入头部,值大向后遍历一次.

// 2 1 3 4 -> 1 2 3 4
List Adjust(List list) {
    // 构造头结点 head -> 2 -> 1-> 3 -> 4
    ListNode* head = (ListNode*) malloc(sizeof(ListNode));
    head->next = list;
    // 获取开始的值
    int beginData = list->data;
    // 遍历时使用的节点
    ListNode* p =  list->next;
    // 用于分隔的节点
    ListNode* pre = list;
    while(p != NULL) {
        if (p->data < beginData) {
            // 记录p的下一个元素,因为要移动p,移动后无法获取下一个元素
            ListNode* q = p->next;
            // 2 1 3 4 ,pre = 2,beginData = 2
            // 首先发现1小于初始元素2,把2和3 4先连接起来
            pre->next = q;
            // 然后将1移动到头部
            p->next = head->next;
            head->next = p;
            p = q;
        } else {
            // 如果p比初始元素要大,直接将p和pre后移
            pre = pre->next;
            p = p->next;
        }
    }
    return head->next;
}

int main() {
    List list = CreateList();
    List newList = Adjust(list);
    PrintList(newList);
}



